Lập trình di truyền

Trong trí tuệ nhân tạo, lập trình di truyền (genetic programming, GP) là một kỹ thuật tiến hóa các chương trình mà ban đầu chưa thích nghi (thường là chương trình ngẫu nhiên) cho đến khi thích nghi được với một nhiệm vụ cụ thể, bằng cách áp dụng các quá trình tương tự di truyền tự nhiên lên quần thể chương trình. Về cơ bản, nó là một kỹ thuật tìm kiếm heuristic thường được mô tả là "leo đồi"[cần dẫn nguồn], tức là tìm kiếm một chương trình tối ưu hoặc ít nhất là phù hợp trong không gian chứa tất cả chương trình.Các quá trình thực hiện bao gồm: chọn lọc các chương trình tốt nhất để sinh sản (trao đổi chéo) và đột biến dựa trên một thang đo độ thích nghi được định nghĩa trước, thường là trình độ thực hiện đối với nhiệm vụ mong muốn. Quá trình trao đổi chéo bao gồm việc hoán đổi các bộ phận ngẫu nhiên của các cặp được chọn (cặp bố mẹ) để tạo ra các thế hệ con mới và khác biệt trở thành một phần của thế hệ chương trình mới. Đột biến là sự thay thế một bộ phận ngẫu nhiên của chương trình bằng một bộ phận ngẫu nhiên khác. Một số chương trình không được chọn để tái tạo được sao chép từ thế hệ hiện tại sang thế hệ mới. Sau đó, quá trình chọn lọc và các quá trình khác được áp dụng đệ quy cho thế hệ chương trình mới.Thông thường, các cá thể của mỗi thế hệ mới trên trung bình thường tốt hơn các cá thể của thế hệ trước đó và chương trình tốt nhất thế hệ cũng thường tốt hơn các chương trình tốt nhất thế hệ của các thế hệ trước. Vòng lặp đệ quy được kết thúc khi xuất hiện cá thể chương trình nào đó đạt đến mức độ thành thạo hoặc độ thích nghi được định trước.Mỗi lần chạy thuật toán có thể và thường xuyên xảy ra sự hội tụ sớm đến điểm cực đại cục bộ nào đó mà không phải là điểm tối ưu toàn cục hoặc thậm chí không phải là nghiệm tốt. Để có được một kết quả rất tốt thường đòi hỏi rất nhiều lần chạy (từ hàng chục tới hàng trăm lần). Ngoài ra, có thể phải tăng kích thước quần thể ban đầu và sự biến đổi của các cá thể để tránh nhiễm gen xấu.

Tài liệu tham khảo

WikiPedia: Lập trình di truyền http://www.cs.mun.ca/~banzhaf/papers/eurogp08_clgp... http://www.idsia.ch/~juergen/diploma.html http://www.geneticprogramming.com http://www.modulusfe.com/products/trading-system-d... //citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1... //citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1... http://ugp3.sourceforge.net/ http://www.sover.net/~nichael/nlc-publications/icg... //doi.org/10.1007%2Fbfb0055930 //doi.org/10.1007%2Fs10710-010-9112-3